package leecode.q0109;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class MyQueue {

    int size = 0;
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {

    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {

        stack1.push(x);
        stack2.clear();
        Stack<Integer> stack3 = new Stack<>();
        for (Integer integer : stack1) {
            stack3.push(integer);
        }
        int size1 = stack1.size() - 1;
        for (int i = 0; i <= size1 - size; i++) {
            stack2.push(stack1.pop());
        }
        stack1 = stack3;
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        ++size;
        return stack2.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        return stack2.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return stack2.isEmpty();
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            if (list.contains(head)) {
                return head;
            }
            list.add(head);
            head = head.next;
        }
        return null;
    }

    public boolean isPalindrome(ListNode head) {
        int length = calc(head);
        int i = 0;
        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            i++;
            if (length % 2 != 0 && i == length / 2 + 1) {
                head = head.next;
                continue;
            }
            if (!stack.isEmpty() && stack.peek() == head.val) {
                stack.pop();
            } else {
                stack.push(head.val);
            }
            head = head.next;
        }
        return stack.isEmpty();
    }

    private int calc(ListNode head) {
        int res = 0;
        while (head != null) {
            res++;
            head = head.next;
        }
        return res;
    }

    private Stack<Integer> calc(ListNode node, Stack<Integer> stack) {
        if (node == null) {
            return stack;
        }

        return calc(node.next, stack);
    }

    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {
            return null;
        }
        List list = new ArrayList<>();
        ListNode cur = head;
        ListNode listNode = new ListNode(cur.val);
        ListNode curNew = listNode;
        list.add(cur.val);
        cur = cur.next;
        while (cur != null) {
            if (!list.contains(cur.val)) {
                list.add(cur.val);
                curNew.next = new ListNode(cur.val);
                curNew = curNew.next;
            }
            cur = cur.next;
        }
        return listNode;
    }
}